package climbstair70

// 思路：
// 动态规划实现：
// 1. 定义状态：dp[i]表示到达第i级台阶的方法数
// 2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
// 3. 初始状态：dp[0] = 1, dp[1] = 1
// 4. 返回值：dp[n]
// 复杂度：O(n)
// 空间复杂度：O(n)
func climbStairs(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

// 优化空间复杂度：
// 1. 定义状态：a表示到达第i-1级台阶的方法数，b表示到达第i级台阶的方法数
// 2. 状态转移方程：a, b = b, a+b
// 3. 初始状态：a = 1, b = 1
// 4. 返回值：b
// 复杂度：O(n)
// 空间复杂度：O(1)
func climbStairs_optimized(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	a, b := 1, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

// 递归实现：
// 1. 定义状态：n表示到达第n级台阶的方法数
// 2. 状态转移方程：f(n) = f(n-1) + f(n-2)
// 3. 初始状态：f(0) = 1, f(1) = 1
// 4. 返回值：f(n)
// 复杂度：O(2^n)
// 空间复杂度：O(n)
func climbStairs_recursive(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	return climbStairs_recursive(n-1) + climbStairs_recursive(n-2)
}
